package com.zklh.leetcode.dynamic;

import java.util.Map;

/**
 * @author ：tong nan
 * @date ：Created in 2021/10/6 14:56
 * @description ：最长回文子序列算法实现,这里使用动态规划实现
 * @modifiedBy ：
 */
public class Solution516 {
    public int longestPalindromeSubseq(String s) {
        // dp[x][y] 表示x,y 区间内 最长回文子序列长度
        int[][] dp = new int[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = 1;
        }

        for (int i = 1; i < s.length(); i++) {
            int x = 0, y = i;
            do {
                if (s.charAt(x) == s.charAt(y)) {
                    dp[x][y] = dp[x + 1][y - 1] + 2;
                } else {
                    dp[x][y] = Math.max(dp[x+1][y], dp[x][y-1]);
                }
                x++; y++;
            } while (y < s.length());
        }

        return dp[0][s.length()-1];
    }

    public static void main(String[] args) {
        Solution516 solution516 = new Solution516();
        System.out.println(solution516.longestPalindromeSubseq("bbbab"));
        System.out.println(solution516.longestPalindromeSubseq("cbbd"));
    }
}
